1. Field of the Invention
The present invention is related to cryptography, and, more particularly, to recovery of encrypted information using a graphical processing unit of a computer as a co-processor.
2. Description of the Related Art
Password recovery, password audits, cryptographic algorithm tasks and cryptographic protocol tasks are all tasks that are extremely demanding on the computational technology. Verifying the correctness of a single password can require tens of thousands of cryptographic transformations, such as hash functions or encryptions. A typical attempt to recover a password or to conduct a password audit requires testing hundreds of millions of passwords, which is a very heavy computational burden on the computer processor.
Traditionally, all such calculations were done on the computer's central processing unit, or CPU, since the hardware and software mechanisms for implementing such operations on other elements of the computer hardware were typically absent. One exception was certain hardware/printed circuit boards, which were specialized for particular tasks (e.g., IBM 4764 PCI-X Cryptographic Coprocessor, Sun Crypto Accelerator 6000 Board, which is typically used to offload SSL processing from CPUs on servers), however, such hardware is generally rare and has not found widespread acceptance. Recently, software began appearing that would take advantage of the capabilities of the graphical processing units (GPUs) of desktop computers. Such graphical processing units are part of a desktop computer's video card. The selection of such GPUs for some of these tasks was not accidental, since working with three-dimensional graphics and rendering of images typically requires advanced computational capabilities.
Thus, just as the capability of the CPUs increases from year to year, the capabilities of the graphics processors also improve continuously from year to year, and the amount of memory available on a typical video card also increases. For example, in 2007, there were video cards available with 1.5 gigabytes of video random access memory. However, earlier approaches to the use of GPUs for some calculation intensive tasks outside of video graphics processing were unsuitable for implementing cryptographic primitives, and therefore, were unsuitable for password recovery and password audit. The problem with GPUs was that they were adapted for processing of floating point calculations, and were generally not suitable for performing integer calculations (or at least, when performing the integer calculations, the performance of a GPU was not sufficiently better than the performance of a CPU).
Such GPUs therefore could not easily work with cryptographic primitives, which require implementing integer functions and integer operations, not floating point operations.